The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
An algorithm is described producing for each formula of the first order theory of algebraically closed fields an equivalent free of quantifiers one. Denote by N a number of polynomials occuring in the formula, by d an upper bound on the degrees of polynomials, by n a number of variables, by a a number of quantifier alternations (in the prefix form). Then the algorithm works within the polynomial in...
We consider the following problem: Given a set Γ = {c1,...,cn} of nonempty strings over a fixed, finite alphabet Σ, is every string in Γ+ uniquely decipherable, or does the equation cx = dy, where c, d ∈ Γ, c ≠ d, and x,y ∈ Γ*, have a solution? We give an O(n L) algorithm for this problem, where L = |c1| + ... + |cn|, and use this algorithm to investigate...
The algebraic theory we present here continues the early work of Chomsky-Schützenberger [Ch,Sch], Shamir [Sh] and Nivat [N]. The leading idea is to develop a machine and production free language theory. The interest in such a theory is support by the hope that the proofs in such a theory don't need so much case discussions which often lead to errors and that a view which is free from non-essentials...
In this paper we consider the relationship between algorithms and parallel VLSI architectures. Starting from the premise that VLSI is the natural habitat for parallel algorithmics, we outline the desirable features of VLSI architectures. Next we discuss the notion of algorithmic paradigm, as the data transfer pattern of a class of specific algorithms. The recursive combination paradigm (applicable...
The Ehrenfeucht Conjecture on test sets states the following: Each language L over some finite alphabet contains a finite subset F (a "test set") such that for each pair (g,h) of homomorphisms it holds g(x) = h(x) for all × in F if and only if g(x) = h(x) for all × in L. In this paper we investigate the connections of this conjecture to its dual form where finite representation for any set...
In a previous paper [BT 83], some probabilistic notions of density and waiting time for a formal language have been studied. We prove here that these probabilistic parameters are computable with an arbitrary precision for some families of languages : the languages with an end marker ; the prefix-free regular sets, with matricial algorithms on Markov chains related to deterministic finite-state automata...
Continuing recent research of [3–9] et al. we study the composition of homomorphisms, inverse homomorphisms and twin-morphisms 〈g,h〉 and 〈g,h〉−1, where 〈g,h〉 (w) = g(w) ∩ h(w) and 〈g,h〉−1 (w) = g−1(w) ∩ h−1 (w). We investigate some properties of these morphic mappings and concentrate on a characterization of the recursively enumerable sets, which says: For every recursively enumerable set L there...
For nondeterministic recursive equations over an arbitrary signature of function symbols including the nondeterministic choice operator "or" the interpretation is factorized. It is shown that one can either associate an infinite tree with the equations, then interprete the function symbol "or" as a nondeterministic choice operator and so mapping the tree onto a set of infinite...
The behaviour of the controlled system determines the control. This concise statement summarizes our approach to the investigation of controls. Using abstract languages to define behaviour and subbehaviour we are able to describe and to study different types of control rules and properties to be realized by control like deadlock avoidance, liveness and fairness.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.